"""
https://leetcode.cn/problems/diagonal-traverse/description/

498. 对角线遍历
中等
相关标签
相关企业
给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

 

示例 1：


输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]
示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]
 

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
-105 <= mat[i][j] <= 105
"""

from typing import List


class Solution:

    def is_boundary(self,row:int,col:int,height:int,width:int)->str:
        rb= row==0 or row==height-1
        cb= col==0 or col==width-1
        if rb:
            if cb: 
                return 'a'
            else:
                return 'r'
        else:
            if cb:
                return 'c'
            else :
                return 'n'


    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        """
        核心是索引切换
        1. ld opr: row+=1,col-=1 on row<height-1 and col>0 and (both then last is ld )
        2. ru opr: row-=1,col+=1 on row>0 and col<width-1 and (both then last is ru)
        3. row push: if row=0 or row=height-1 then row+=1
        4. col down: if col=0 or col=width-1 then col+=1
        5. end: if row=height-1 and col=width-1

        1. 排序规则，从0开始，直到w+h-2，即为max_sum
        2. 如果和是sum，则其中条数是min(sum,max_sum-sum)+1
        3. 某个sum的最小row是max(0,sum-w+1),最小col是max(0,sum-h+1)
        4. 根据2和3可以推测出，某个sum的最大row是min(sum,max_sum-sum)-max(0,sum-w+1)
        5. 当sum为偶数时，从最小的row开始，当sum为奇数时，从最大的row开始

        """
        h=len(mat)
        w=len(mat[0])
        
        max_sum=w+h-2
        res_list=[]
        for sum in range(max_sum+1):
            print(f'sum={sum}')
            count=min(sum,max_sum-sum)+1
            min_row=max(0,sum-w+1)
            max_row=min_row+count-1
            if sum%2==1:
                for row in range(min_row,max_row+1):
                    col=sum-row
                    print(f'r:{row},c:{col}')
                    res_list.append(mat[row][col])
            else:
                for row in range(max_row,min_row-1,-1):
                    col=sum-row
                    print(f'r:{row},c:{col}')
                    res_list.append(mat[row][col])
        
        return res_list



if __name__=='__main__':
    sol=Solution()
    mat = [[6,9,7]]
    res=sol.findDiagonalOrder(mat)
    print(res)